/**
 * 105. 从前序与中序遍历序列构造二叉树
 * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 */
const { TreeNode, displayTreeNode } = require('../../libs/public');

/**
 * @param {number[]} preorder
 * @param {number} preBegin
 * @param {number} preEnd
 * @param {number[]} inorder
 * @param {number} inBegin
 * @param {number} inEnd
 */
function buildSubTree(preorder, preBegin, preEnd, inorder, inBegin, inEnd) {
  if (preBegin > preEnd) {
    return null;
  }
  if (preBegin === preEnd) {
    return new TreeNode(preorder[preBegin]);
  }
  const root = new TreeNode(preorder[preBegin]);
  const index = inorder.indexOf(preorder[preBegin], inBegin);
  const leftCount = index - inBegin;
  root.left = buildSubTree(preorder, preBegin + 1, preBegin + leftCount, inorder, inBegin, index - 1);
  root.right = buildSubTree(preorder, preBegin + leftCount + 1, preEnd, inorder, index + 1, inEnd);
  return root;
}

/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
function buildTree(preorder, inorder) {
  return buildSubTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}

console.log(displayTreeNode(buildTree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])) === '[3,9,20,null,null,15,7]');
console.log(displayTreeNode(buildTree([-1], [-1])) === '[-1]');
